package density.utils;

import density.model.Cluster;
import density.model.DataPoint;
import density.model.Rectange;

import java.io.*;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by jiangyangbo on 2017/9/21.
 */
public class DBSCAN {
    private List<DataPoint> dataSet;
    private double eps;
    private int minPts;

    /**
     * 构造函数
     * @param minPts 聚簇的最小单位
     * @param eps 距离值
     * @param dataSet 需要计算的坐标集合
     */
    public DBSCAN(int minPts, double eps, List<DataPoint> dataSet) {
        this.minPts = minPts;
        this.eps = eps;
        this.dataSet = dataSet;
    }

    public void init(String dataPath) throws IOException {
        if(dataPath==null)
            throw new RuntimeException("缺少测试数据文件！");
        File file = new File(dataPath);
        if (!file.exists()) {
            throw new RuntimeException("测试数据文件不存在！");
        }
        InputStreamReader reader = new InputStreamReader(new FileInputStream(file), "utf-8");
        BufferedReader bufferedReader = new BufferedReader(reader);
        String row = bufferedReader.readLine();
        while (row!=null) {
            String[] rdata = row.split("\t");
            dataSet.add(new DataPoint(Double.parseDouble(rdata[0].trim()), Double.parseDouble(rdata[1].trim())));
            row = bufferedReader.readLine();
        }
    }

    public List<Cluster> dBScan() {
        int i = 0;
        List<Cluster> clusterList = new LinkedList<Cluster>();
        for (DataPoint p : dataSet) {
            if (p.isVisited()) continue;
            //设置该点已经被访问
            p.setIsVisited(true);
            List<DataPoint> neighborPts = new LinkedList<DataPoint>();
            boolean isCorePoint = isCorePoint(p, neighborPts);
            if (!isCorePoint)
                //标记为噪音数据
                p.setIsNoise(true);
            else {
                //作为核心点，根据该点创建一个类别
                p.setIsCore(true);
                Cluster cluster = new Cluster("cluset@" + i++, p);
                clusterList.add(cluster);
                expandCluster(p, neighborPts, cluster);
            }
        }
        return clusterList;
    }



    /**
     * 根据核心点扩展
     *
     * @param corePoint   核心点
     * @param neighborPts 密度相连点
     * @param cluster     核心点的簇
     */
    private void expandCluster(DataPoint corePoint, List<DataPoint> neighborPts, Cluster cluster) {
        cluster.addMemberNotExists(corePoint);
        List<DataPoint> nPts;
        Queue<DataPoint> neighborPtQueue = new LinkedList<DataPoint>(neighborPts);
        DataPoint neighborPt=null;
        while (neighborPtQueue.size() > 0) {
            neighborPt = neighborPtQueue.poll();
            cluster.addMemberNotExists(neighborPt);
            //然后针对核心点邻域内的点，如果该点没有被访问
            if (!neighborPt.isVisited()) {
                nPts = new LinkedList<DataPoint>();
                neighborPt.setIsVisited(true);
                boolean isCorePoint = isCorePoint(neighborPt, nPts);
                if (isCorePoint) {
                    neighborPt.setIsCore(true);
                    neighborPtQueue.addAll(nPts);
                }
            }
        }
    }

    /**
     * 查询指定点指定半径内的相邻点
     *
     * @param p
     * @return
     */
    private boolean isCorePoint(DataPoint p, List<DataPoint> neighborPts) {
        Rectange outRectange = new Rectange(p, eps);
        List<DataPoint> rectNeighborPts = new LinkedList<DataPoint>();
        //外接矩形内点
        for (DataPoint point : dataSet) {
            if (outRectange.containPoint(point))
                rectNeighborPts.add(point);
        }
        if (rectNeighborPts.size() < minPts) return false;
        //内接水平矩形内的点
        //d表示内接矩形的长的一半
        double d = Math.sin(45.0) * eps;
        double left = p.getX() - d;
        double top = p.getY() + d;
        double right = p.getX() + d;
        double bottom = p.getY() - d;
        Rectange innerRectance = new Rectange(left, right, top, bottom, p);


        //在内接矩形内的点肯定也在圆内
        for (int i = 0; i < rectNeighborPts.size(); i++) {
            DataPoint point = rectNeighborPts.get(i);
            if (innerRectance.containPoint(point)) {
                neighborPts.add(rectNeighborPts.remove(i));
                i--;
            }
        }
        //对于剩余的点再做距离判断
        for (DataPoint point : rectNeighborPts) {
            double distance = getDistance(p, point);
            if (distance <= eps)
                neighborPts.add(point);
        }
        return neighborPts.size() > minPts;
    }
    
//    private boolean isCorePoint(DataPoint p, List<DataPoint> neighborPts) {
//
//        for(DataPoint dp : dataSet){
//           double distance= getDistance(p, dp);
//           if(distance<=eps){
//               neighborPts.add(dp);
//           }
//        }
//        return neighborPts.size() > minPts;
//
//    }
    private static double getDistance(DataPoint dp1,DataPoint dp2){
      double distance=0.0;
      distance += Math.pow((dp1.getX()-dp2.getX()), 2);
      distance += Math.pow((dp1.getY()-dp2.getY()), 2);
      distance=Math.pow(distance, 0.5);
      return distance;
//      return Earth.getDistance2(dp2, dp1);
  }    
//    
//    /**
//     * @param args
//     */
//    public static void main(String[] args) throws IOException  {
//        double eps = 0.0036;
//        for (int i = 1; i<=5; i++) {
//            DBSCAN scan = new DBSCAN(1, eps);
//            scan.init("d:/temp/xy07/xy" + i + ".txt");
//            List<Cluster> clusters = scan.dBScan();
//            int max = 0;
//            Cluster maxCluster = null;
//            for (Cluster cluster : clusters) {
//                max = Math.max(max, cluster.getMembers().size());
//                if (cluster.getMembers().size() == max) {
//                    maxCluster = cluster;
//                }
//            }
//            max = getMax(maxCluster, eps);
//            for (Cluster cluster : clusters) {
//                if (cluster.getMembers().size() > max && !cluster.equals(maxCluster)) {
//                    max = Math.max(max, getMax(cluster, eps));
//                }
//            }            
//            System.out.println("xy " + i + " max:" + max );
//            
////            int max = getMax(scan.dataSet);
////            System.out.println("xy " + i + " max:" + max );
//        }
//    }    
//    public static int getMax(List<DataPoint> dataSet) {
//        //获取簇集左上角坐标 和 右下角坐标
//        double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE, maxX = Double.MIN_VALUE, maxY = Double.MIN_VALUE;
//        for (DataPoint dp : dataSet) {
//            minX = Math.min(minX, dp.getX());
//            minY = Math.min(minY, dp.getY());
//            maxX = Math.max(maxX, dp.getX());
//            maxY = Math.max(maxY, dp.getY());
//        }
//        //以10米为步长开始遍历
//        int max = 0;
//        for (double x = minX; x < maxX; x += 10) {
//            for (double y = minY; y < maxY; y += 10) {
//                int density = 0;
//                for (DataPoint dp : dataSet) {
//                    if (dp.getX() >= x && dp.getX() <= x + 200 && dp.getY() >= y && dp.getY() <= y + 200) {
//                        density++; 
//                    }
//                }
//                max = Math.max(max, density);
//            }
//        }
//        return max;
//    }
//    
//    public static int getMax(Cluster cluster, double eps) {
//        //获取簇集左上角坐标 和 右下角坐标
//        double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE, maxX = Double.MIN_VALUE, maxY = Double.MIN_VALUE;
//        for (DataPoint dp : cluster.getMembers()) {
//            minX = Math.min(minX, dp.getX());
//            minY = Math.min(minY, dp.getY());
//            maxX = Math.max(maxX, dp.getX());
//            maxY = Math.max(maxY, dp.getY());
//        }
//        //以10米为步长开始遍历
//        int max = 0;
//        double step = eps / 20;
//        for (double x = minX; x < maxX; x += step) {
//            for (double y = minY; y < maxY; y += step) {
//                int density = 0;
//                for (DataPoint dp : cluster.getMembers()) {
//                    if (dp.getX() >= x && dp.getX() <= x + eps && dp.getY() >= y && dp.getY() <= y + eps) {
//                        density++; 
//                    }
//                }
//                max = Math.max(max, density);
//            }
//        }
//        return max;
//    }
    
//    private void ToGeo(List<DataPoint> Data) {
//
//        List<double[]> data = PrjToGeo.BJ54PrjToGeo(Data.Select<EventPosition, double[]>((<>c.<>9__11_0 = new Func<EventPosition, double[]>(<>c.<>9.<ToGeo>b__11_0))).ToList<double[]>());
//        for (int i = 0; i < Data.Count<EventPosition>(); i++)
//        {
//            double y;
//            double x;
//            Data[i].POS_X = data[i][0];
//            Data[i].POS_Y = data[i][1];
//            EvilTransform.GpsToBaidu(Data[i].POS_Y, Data[i].POS_X, out y, out x);
//            Data[i].POS_X = x;
//            Data[i].POS_Y = y;
//        }
//    }
}
